#define _CRT_SECURE_NO_WARNINGS 1

struct Node* copyRandomList(struct Node* head)
{
    struct Node* tail = head;
    while (tail)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = tail->val;
        copy->next = tail->next;
        tail->next = copy;
        tail = copy->next;
    }
    tail = head;
    while (tail)
    {

        struct Node* copy = tail->next;
        if (tail->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = tail->random->next;
        }
        tail = tail->next->next;
    }
    tail = head;
    struct Node* newhead = NULL, * cur = NULL;
    while (tail)
    {
        struct Node* copy = tail->next;
        struct Node* next = copy->next;
        if (newhead == NULL)
        {
            newhead = cur = copy;
        }
        else
        {
            cur->next = copy;
            cur = cur->next;
        }
        tail = next;
    }
    return newhead;
}